package com.blankj.easy._0026;

/**
 * <pre>
 *     author: Blankj
 *     blog  : http://blankj.com
 *     time  : 2017/04/30
 *     desc  : 删除有序数组中的重复项
 *
 * 描述：给定一个有序数组 nums。
 * 要求：删除数组 nums 中的重复元素，使每个元素只出现一次。并输出去除重复元素之后数组的长度。
 *
 * 不能使用额外的数组空间，在原地修改数组，并在使用O(1)额外空间的条件下完成。
 *
 * 1.定义两个快慢指针 slow，fast。其中 slow 指向去除重复元素后的数组的末尾位置。fast 指向当前元素。
 * 2.令 slow 在后， fast 在前。令 slow = 0，fast = 1。
 * 3.比较 slow 位置上元素值和 fast 位置上元素值是否相等。如果不相等，则将 slow 后移一位，将 fast 指向位置的元素复制到 slow 位置上。
 * 4.将 fast 右移 1 位。
 * 5.重复上述 3 ~ 4 步，直到 fast 等于数组长度。
 * 6.返回 slow + 1 即为新数组长度。
 * </pre>
 */
public class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len <= 1) return len;
        int tail = 1;
        for (int i = 1; i < len; ++i) {
            if (nums[i - 1] != nums[i]) {
                nums[tail++] = nums[i];
            }
        }
        return tail;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] data = new int[]{0, 1, 1, 2, 3, 3, 3};
        int len = solution.removeDuplicates(data);
        System.out.println("len: "+ len);
        for (int i = 0; i < len; i++) {
            System.out.print(data[i] + (i == len - 1 ? "" : ", "));
        }
    }
}
